package leetcode.code139;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution extends Solution139 {

	private class DicNode {
		public DicNode(char c) {
			this.c = c;
		}

		public char c;
		public DicNode[] next = new DicNode[128];
		public boolean isEnd;

		public DicNode hasChar(char c) {
			return next[c];
		}

		public DicNode setChar(char c) {
			if (next[c] == null) {
				DicNode dn = new DicNode(c);
//				dn.pre = this;
				next[c] = dn;
				return dn;
			}
			return next[c];
		}

//		public DicNode pre;

	}

	private DicNode buildDicTree(List<String> wordDict) {
		DicNode head = new DicNode('*');
		for (String wd : wordDict) {
			DicNode dn = null;
			for (char c : wd.toCharArray()) {
				if (dn == null) {
					dn = head.setChar(c);
				} else {
					dn = dn.setChar(c);
				}
			}
			dn.isEnd = true;
		}
		return head;
	}

	@Override
	public boolean wordBreak(String s, List<String> wordDict) {
		DicNode head = this.buildDicTree(wordDict);
		char[] chars = s.toCharArray();
		return this.wordBreak(head, chars, 0);
	}

	public boolean wordBreak(DicNode head, char[] chars, int start) {
		// leetcode
		DicNode dn = null;
		Queue<Integer> q = new LinkedList<>();// 记录需要尝试的单词的开头
//		Set<Integer> set = new HashSet<>();
		for (int i = start; i < chars.length; i++) {
			char c = chars[i];
			if (dn == null) {// 一个新词
				dn = head.hasChar(c);
			} else {
				dn = dn.hasChar(c);
			}
			if (dn != null && dn.isEnd) {
				if (i == chars.length - 1)
					return true;
				else if (i + 1 < chars.length && dn.hasChar(chars[i + 1]) != null) {
//					set.add(i);
					if(!q.contains(i)) {
						q.add(i);
					}
				} else
					dn = null;
			} else if (dn == null || (i == chars.length - 1 && !dn.isEnd)) {// dn没找到，或者来到最后一位
				if (q.isEmpty())
					return false;
				else {
					i = q.poll();
					dn = null;
				}
			}
		}
		return false;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1("leetsscode");
		so.debug2();
		so.debug3();
		so.debug4();
//		System.out.println((int) 'a');
//		System.out.println((int) 'z');
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

}
